package com.ayuer.chapter10;


import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class CoinChangeDemo {
    public static void main(String[] args) {
        // 每次循环时，找到当前最优解，它凑出的硬币大小
        int res = coinChange(new int[]{5, 2, 1}, 5);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        System.out.println(res);
    }

    /**
     * 有可能会出错
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        int remainder = amount;
        int count = 0;
        for (int coin : coins) {
            // 每次选择最优的解
            while (remainder >= coin) {
                remainder -= coin;
                count++;
            }
            if (remainder == 0) {
                return count;
            }
        }
        if (remainder >= 0) {
            //没凑成功
            return -1;
        }
        return count;
    }
}
